package arithmetic.demo19;

/**
 * 动态规划：区间dp + 分类讨论 + 正难则反 + 最长公共子序列：两个字符串的最小AscLL和
 */
class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        // 动态规划 + 分类讨论 + 正难则反

        // 长度
        int len1 = s1.length() , len2 = s2.length();

        // 创建 dp
        int[][] dp = new int[len1+1][len2+1];
        s1 = " " + s1; s2 = " " + s2;
        // 转化为字符数组操作             
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();        
        
        int sum = 0;
        // 计算总数目
        for(int i = 1; i <= len1;i++) {
            sum += str1[i];
        }
        for(int i = 1; i <= len2;i++) {
            sum += str2[i];
        }
        // 初始化
        // 从上往下，从左往右填表
        for(int i = 1; i <= len1; i++) {
            for(int j = 1; j <= len2; j++) {         
                // 正难则反   
                dp[i][j] = str1[i] == str2[j] ? dp[i-1][j-1] + str1[i] + str2[j]  : 
               Math.max(dp[i-1][j]  , dp[i][j-1]);
            }
        } 

        
        // 返回最终 总和 - 最大和的子序列ASCLL 和
        return sum - dp[len1][len2];
    }    
}

/**
 * 动态规划 ： 区间dp + 分类讨论 + 取dp 钟的最大值： 最长重复子数组
 */

class Solution1 {
    public int findLength(int[] nums1, int[] nums2) {
        // 动态规划 + 分类讨论
        int len1 = nums1.length, len2 = nums2.length;

        // 创建 dp
        int[][] dp = new int[len1 + 1][len2 + 1];

        int ret =  0;
        // 填表
        for(int i = 1; i <= len1; i++) {
            for(int j = 1; j <= len2; j++) {
                if(nums1[i-1] == nums2[j-1]) {
                    // 如果相等就+1 像上走
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    // 如果不相等就用 0 来截断
                    dp[i][j] = 0;
                }
                // 更新最大值
                ret = Math.max(dp[i][j],ret);

            }
        }
        // 确定返回值
        return ret;
    }
}